package luogu;


import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class A8802 {
    static int n;
    static int m;
    static int N=1050;
    static int M=10010;
    static int[] h=new int[N];
    static int[] e=new int[M];
    static int[] ne=new int[M];
    static int[] w=new int[M];
    static int idx=1;
    static boolean[] st=new boolean[N];
    static int[] time=new int[N];
    static int[] dist=new int[N];//最短路数组
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] s = read.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        String[] s1 = read.readLine().split(" ");
        //时间
       for(int i=1;i<=n;i++){
           time[i]=Integer.parseInt(s1[i-1]);
       }
       time[1]=0;
        //录入边
        for(int i=1;i<=m;i++){
            String[] s2 = read.readLine().split(" ");
            int a=Integer.parseInt(s2[0]);
            int b=Integer.parseInt(s2[1]);
            int c=Integer.parseInt(s2[2]);
            //a到达b的时间等于c+time[b]
add(a,b,c+time[b]);
add(b,a,c+time[a]);
        }
dijkStar();

      log.write(Integer.toString(dist[n]-time[n]));
      log.flush();
        //最后输出的时间应该减去到达N的time[N]
    }
    static void add(int a,int b,int c)
    {
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
    }
    static void dijkStar(){
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1]=0;
        PriorityQueue<int[]> heap=new PriorityQueue<>((a, b)->{return a[0]-b[0];});//小根堆i
        //入
        heap.offer(new int[]{0,1});//距离，编号
        while(!heap.isEmpty()){
            int[] poll = heap.poll();
            int ver=poll[1];
            int distance=poll[0];//距离
            if(st[ver])continue;//已经收集最短距离则跳过
            //标记为已获得最短距离
            st[ver]=true;
            //更新
            for(int edge=h[ver];edge!=0;edge=ne[edge]){
                int end=e[edge];
                //如果到达ta
                if(dist[end]>distance+w[edge]){
                    //更新最短距离
                    dist[end]=distance+w[edge];
                    //加入队列
                    heap.offer(new int[]{dist[end],end});
                }
            }
        }


        //将第一个
    }
    }


